//
// Description: 6014. 构造限制重复的字符串
// Created by Loading on 2022/2/20.
//

#include <bits/stdc++.h>

using namespace std;

string repeatLimitedString(string s, int repeatLimit) {
    // 统计次数
    unordered_map<int, int> m;
    for (auto c : s) {
        m[c]++;
    }

    string res;
    for (int i = 'z'; i >= 'a'; --i) {
        while (m[i] > 0) {
            int _min = min(repeatLimit, m[i]);
            res.append(_min, i);
            m[i] -= _min;
            if (m[i]) {// 当前最大字符未使用完毕，选择一个次大的做间隔
                bool flag = false; // 是否找到次大的
                for (int j = i - 1; j >= 'a'; --j) {
                    if (m[j]) {// 找到次大值，使用一个
                        res.append(1, j);
                        m[j]--;
                        flag = true;
                        break;
                    }
                }
                if (!flag) {// 未找到次大值，直接跳出循环
                    break;
                }
            }
        }
    }

    return res;
}

int main() {
    string s = "aababab";
    int repeatLimit = 2;
    auto res = repeatLimitedString(s, repeatLimit);
    cout << res << endl;

    return 0;
}